`
https://leetcode.cn/problems/advantage-shuffle/
`

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var advantageCount = function (nums1, nums2) {
  const n = nums1.length

  // 使用最大堆存储 num2，降序排序
  const maxpq = new Heap((a, b) => b[1] - a[1])
  for (let i = 0; i < n; i++) {
    maxpq.push([i, nums2[i]])
  }

  // 给 num1 升序排序
  nums1.sort((a, b) => a - b)

  // nums1[left] 是最小值，nums1[right] 是最大值
  let left = 0, right = n - 1
  const res = new Array(n).fill(0)

  while (!maxpq.isEmpty()) {
    let pair = maxpq.pop()
    // maxval 是 nums2 中的最大值，i 是对应索引
    let i = pair[0], maxval = pair[1];
    if (maxval < nums1[right]) {
      // 如果 nums1[right] 能胜过 maxval，那就自己上
      res[i] = nums1[right];
      right--;
    } else {
      // 否则用最小值混一下，养精蓄锐
      res[i] = nums1[left];
      left++;
    }
  }

  return res
};

class Heap {
  constructor(compare) {
    this.heap = [];
    this.compare = compare;
  }
  size() {
    return this.heap.length;
  }
  isEmpty() {
    return this.heap.length === 0;
  }
  push(value) {
    this.heap.push(value);
    this.bubbleUp(this.heap.length - 1);
  }
  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.compare(this.heap[index], this.heap[parentIndex]) < 0) {
        [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
        index = parentIndex;
      } else break;
    }
  }
  pop() {
    if (this.isEmpty()) return undefined;
    const top = this.heap[0];
    const last = this.heap.pop();
    if (!this.isEmpty()) {
      this.heap[0] = last;
      this.sinkDown(0);
    }
    return top;
  }
  sinkDown(index) {
    let current = index;
    const length = this.size();
    while (true) {
      const left = 2 * current + 1;
      const right = 2 * current + 2;
      let target = current;
      if (left < length && this.compare(this.heap[left], this.heap[target]) < 0)
        target = left;
      if (right < length && this.compare(this.heap[right], this.heap[target]) < 0)
        target = right;
      if (target !== current) {
        [this.heap[current], this.heap[target]] = [this.heap[target], this.heap[current]];
        current = target;
      } else break;
    }
  }
}